1584C - Two Arrays - CodeForces Solution


greedy math sortings *900

Please click on ads to support us..

Python Code:


t = int(input())
testcases = []

for _ in range(t):
    n = int(input())
    x = list(map(int, input().split()))
    y = list(map(int, input().split()))
    testcases.append((x,y))
    

def checkOne(arr,targ,val):
    
    can = val
    
    l1 = 0
    l2 = 0
    
    while l1 < len(arr):
        if arr[l1] == targ[l2]:
            l1 += 1
            l2 += 1
        else:
            if arr[l1]+1 == targ[l2] and can > 0:
                l1 += 1
                l2 += 1
                can -= 1
            else:
                return False
    
    return True
                
        
def checkPossible(curr,target):
        for i in range(len(curr)+1):
                if checkOne(curr,target,i):
            return 'YES'
    return 'NO'
    
for c,t in testcases:
    c.sort()
    t.sort()
    x = checkPossible(c,t)
    print(x)
        
        

C++ Code:

#include<bits/stdc++.h>
using namespace std;
#define int 						  long long
#define ld 							  long double
#define nline						  "\n"
#define ff 							  first
#define ss                            second
#define pb                            push_back
#define int                           long long
#define fl(i,k,n)                     for (int i = k; i < n; i++)
#define rfl(i,n, k)                   for (int i = n; i >= k; i--)
#define fel(a,x)                      for (auto& a : x)
#define mp                            make_pair
#define ppb 						  pop_back
#define ps(x, y)                      fixed << setprecision(y) << x
#define setbit(x)                     __builtin_popcount(x);
#define all(var)                      var.begin(), var.end()
#define desc                          greater<int>()
#define spc                           <<" "<<
#define YES                           cout << "YES\n";
#define NO                            cout << "NO\n";
#define Yes                           cout << "Yes\n";
#define No                            cout << "No\n";
#define minus1                        cout << "-1\n";
#define one                           cout << "1\n";
#define gcd(a, b)                     __gcd(a, b)
#define PI                            3.141592653589793238462
#define sz(x) (                       (int)(x).size())
#define jay_shri_ram                  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

// Builtin data types
typedef pair<int, int> 	              pii     ;
typedef vector<int>                   vi      ;
typedef vector<string>                vs      ;
typedef vector<pii> 				  vpi     ;
typedef vector <pair<int , int> >     vpi     ;
typedef vector<bool>                  vb      ;
typedef vector<vector<int>>           vvi     ;
typedef map<int, int> 				  mpii    ;
typedef set<int>   					  seti    ;
typedef multiset<int> 				  mseti	  ;
typedef unordered_set<int>            useti   ;
typedef unordered_map<int, int>       umapii  ;
typedef unsigned long long            ull     ;
//constants
const int MAX_N = 1e5 + 5;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int EPS = 1e-9;

//debugger
#ifndef ONLINE_JUDGE
#define db(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define db(x)
#endif
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(ld t) {cerr << t;}
void _print(double t) {cerr << t;}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V>
void _print(pair <T, V> p) {
	cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";
}
template <class T>
void _print(vector <T> v) {
	cerr << "[ ";
	for (T i : v) {
		_print(i);
		cerr << " ";
	}
	cerr << "]";
}
template <class T>
void _print(set <T> v) {
	cerr << "[ ";
	for (T i : v) {
		_print(i);
		cerr << " ";
	}
	cerr << "]";
}
template <class T>
void _print(multiset <T> v) {
	cerr << "[ ";
	for (T i : v) {
		_print(i);
		cerr << " ";
	}
	cerr << "]";
}
template <class T, class V>
void _print(map <T, V> v) {
	cerr << "[ ";
	for (auto i : v) {
		_print(i);
		cerr << " ";
	}
	cerr << "]";
}
//-------------------------------Think&Code----------------------------------*/


void solve() {
	int n  ; cin >> n ;
	vi arr(n), brr(n);
	multiset<int> ms ;
	for (int i = 0 ; i < n; i++) {cin >> arr[i]; }
	for (int i = 0 ; i < n; i++) {cin >> brr[i] ; ms.insert(brr[i]);}
	if (arr == brr) {
		YES
		return ;
	}
	db(arr);
	db(ms);
	sort(all(arr));
	sort(all(brr));
	for (int i = 0 ; i < n; i ++) {
		if (ms.count(arr[i]) ) {
			ms.erase(ms.find(arr[i]));
		}
		else {
			if (ms.count(arr[i] + 1) ) {
				ms.erase(ms.find(arr[i] + 1));
			}
		}
	}
	if (ms.empty()) {
		YES
	} else {
		NO
	}

}
int32_t main() {
#ifndef ONLINE_JUDGE
	freopen("Error.txt", "w", stderr);
#endif
	jay_shri_ram;

	int t ; cin >> t;
	//int t=1;

	while (t--) {
		solve();
	}
}
/* -----------------END OF PROGRAM --------------------*/



Comments

Submit
0 Comments
More Questions

1725G - Garage
1725B - Basketball Together
735A - Ostap and Grasshopper
1183B - Equalize Prices
1481A - Space Navigation
1437B - Reverse Binary Strings
1362B - Johnny and His Hobbies
1299A - Anu Has a Function
1111A - Superhero Transformation
954A - Diagonal Walking
39F - Pacifist frogs
1451C - String Equality
386A - Second-Price Auction
1690E - Price Maximization
282B - Painting Eggs
440A - Forgotten Episode
233B - Non-square Equation
628B - New Skateboard
262B - Roma and Changing Signs
755C - PolandBall and Forest
456B - Fedya and Maths
376B - IOU
1623B - Game on Ranges
1118A - Water Buying
1462C - Unique Number
301A - Yaroslav and Sequence
38A - Army
38C - Blinds
1197A - DIY Wooden Ladder
1717D - Madoka and The Corruption Scheme